/* 本文件中所有函数的使用方法均与qsort函数完全相同 */
#include <stdio.h>
#include <alloca.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include "kernel_list.h"
#include "interface.h"

void *BINARY_SEARCH_ALL(void *base, size_t nmemb, size_t size, const void *searchmem, 
		int (*compar)(const void *, const void *));

/* 
 * INSERTION_SORT函数为插入排序函数,采用顺序查找插入点的方式,
 * 该函数的使用方法同qsort函数
 */
void INSERTION_SORT(void *base, size_t nmemb, size_t size, 
		int (*compar)(const void *, const void *))
{
	void *j = base + size;
	void *i = NULL, *key = NULL;
	key = alloca(size);

	for (; j < base + size * nmemb; j += size) {
		memcpy(key, j, size);
		i = j - size;
		while (i >= base && compar(i, key) > 0) {
			memmove(i + size, i, size);
			i -= size;
		}
		if (i < j - size) {
			memmove(i + size, key, size);
		}
	}
}

/*
 * 使用二分查找的插入排序
 */
void INSERTION_SORT_BINARY_SEARCH(void *base, size_t nmemb, size_t size,
		int (*compar)(const void *, const void *))
{
	void *j = base + size;
	void *key = alloca(size);
	void *p = NULL;
	int num, i;

	for (; j < base + size * nmemb; j += size) {
		memcpy(key, j, size);
		num = (j - base) / size;
		p = BINARY_SEARCH_ALL(base, num, size, key, compar);
		num = (j - p - size) / size;
		i = 0;
		if (num > 0) {
			memmove(p + size + size, p + size, num * size);
			memcpy(p + size, key, size);
		}
	}
}

/* 
 * 二分查找 
 * 如果存在,返回该节点的首地址
 * 如果不存在,返回应当插入的位置,返回值+size即为插入位置
 */
void *BINARY_SEARCH_ALL(void *base, size_t nmemb, size_t size, const void *searchmem, 
		int (*compar)(const void *, const void *))
{
	void *p = NULL;
	void *top = NULL;
	void *mid = NULL;
	int order;
	int ret1, ret2, tmp;
	unsigned int tmp2;

	if (base == NULL) {
		return NULL;
	}
	if (nmemb == 0) {
		return base - size;
	}
	if (searchmem == NULL)
		return NULL;
	top = base + size * (nmemb - 1);
	mid = base + (nmemb - 1) / 2 * size;
	order = compar(base, top);
	
	if (order < 0) {
		ret1 = compar(searchmem, top);
		ret2 = compar(searchmem, base);
		if (ret1 > 0 || ret2 < 0) {
			if (ret1 > 0)
				p = top;
			if (ret2 < 0)
				p = base - size;
			goto end;
		}
		else if (ret1 == 0 || ret2 == 0) {
			if (ret1 == 0)
				p = top;
			if (ret2 == 0)
				p = base;
			goto end;
		}
		while (base < top - size) {
			ret1 = compar(searchmem, mid);
			if (ret1 < 0) {
				top = mid;
			}
			else if (ret1 > 0) {
				base = mid;
			}
			else {
				p = mid;
				goto end;
			}
			tmp2 = (top - base) / 2;
			if (!(tmp = tmp2 % size))
				mid = base + tmp2;
			else mid = base + tmp2 + size - tmp;
		}
		p = base;
	}
	else if (order > 0) {
		ret1 = compar(searchmem, top);
		ret2 = compar(searchmem, base);
		if (ret1 < 0 || ret2 > 0) {
			if (ret1 < 0)
				p = top;
			if (ret2 > 0)
				p = base - size;
			goto end;
		}
		else if (ret1 == 0 || ret2 == 0) {
			if (ret1 == 0)
				p = top;
			if (ret2 == 0)
				p = base;
			goto end;
		}
		while (base < top - size) {
			ret1 = compar(searchmem, mid);
			if (ret1 < 0) {
				base = mid;
			}
			else if (ret1 > 0) {
				top = mid;
			}
			else {
				p = mid;
				goto end;
			}
			tmp2 = (top - base) / 2;
			if (!(tmp = tmp2 % size))
				mid = base + tmp2;
			else mid = base + tmp2 + size - tmp;
		}
		p = base;
	}
	else p = base;
end:
	return p;
}

/* array1与array2必须是连续的空间,且array1在array2之前 */
static void MERGE(void *array1, size_t nmemb1, void *array2, size_t nmemb2,
		size_t size, int (*compar)(const void *, const void*))
{
	void *i = array1, *j = array2, *k = i;
	void *end1 = array1 + nmemb1 * size;
	void *end2 = array2 + nmemb2 * size;
	void *tmp_array = NULL;
	int len;
	
	while (i < end1 && j < end2) {
		if (compar(i, j) > 0) {
			if (tmp_array == NULL) {
				len = end1 - i;
				tmp_array = malloc(len);
				memcpy(tmp_array, i, len);
				i = tmp_array;
				end1 = i + len;
			}
			memcpy(k, j, size);
			j += size;
		}
		else {
			if (tmp_array) {
				memcpy(k, i, size);
			}
			i += size;
		}
		k += size;
		if (j == end2 && tmp_array) {
			memcpy(k, i, end1 - i);
		}
	}
	if (tmp_array)
		free(tmp_array);
}
/* 合并排序 */
void MERGE_SORT(void *base, size_t nmemb, size_t size,
		int (*compar)(const void *, const void *))
{
	if (nmemb <= 0)
		return;
	int depth = (int)(ceil(log2(nmemb)));
	int num1 = 1, num2 = 1, tmp, remain_num;
	int node_num = nmemb;
	int end_marge_flag, end_num;
	void *array1 = base, *array2 = base + size;
	
	remain_num = 0;
	end_num = 1;
	while (depth) {
		tmp = node_num / 2;
		end_marge_flag = !(node_num % 2);
		for (array1 = base, array2 = base + num1 * size; tmp; tmp--) {
			if (end_marge_flag) {
				if (!(tmp - 1) && end_num) {
					num2 = end_num;
					end_num = num1 + num2;
				}
			}
			MERGE(array1, num1, array2, num2, size, compar);
			array1 += num1 * size + num2 * size;
			array2 += num2 * size + num1 * size;
		}
		num1 <<= 1;
		num2 = num1;
		node_num = (node_num % 2) ? node_num / 2 + 1 : node_num / 2;
		depth--;
	}
}

/* 堆排序 */
/* 保持堆的性质,描述见《算法导论》第六章 */
static void HEAPIFY(void *base, size_t nmemb, size_t size, 
		int (*compar)(const void *, const void *), void *index)
{
	void *end = base + nmemb * size;
	void *tmp = alloca(size);
	void *left = LEFT(base, index, size);
	void *right = RIGHT(base, index, size);
	void *largest = NULL;

	for (; left < end || right < end; left = LEFT(base, index, size), right = RIGHT(base, index, size)) {
		if (left < end && compar(left, index) > 0) 
			largest = left;
		else largest = index;
		if (right < end && compar(right, largest) > 0)
			largest = right;
		if (largest == index)
			break;
		memcpy(tmp, index, size);
		memcpy(index, largest, size);
		memcpy(largest, tmp, size);
		index = largest;
	}
}

static void BUILD_HEAP(void *base, size_t nmemb, size_t size,
		int (*compar)(const void *, const void *))
{
	void *i;
	for (i = (nmemb / 2 - 1) * size + base; i >= base; i -= size) {
		HEAPIFY(base, nmemb, size, compar, i);
	}
}

void HEAP_SORT(void *base, size_t nmemb, size_t size,
		int (*compar)(const void *, const void *))
{
	void *i;
	void *tmp = alloca(size);
	int heap_size = nmemb;
	BUILD_HEAP(base, nmemb, size, compar);
	for (i = (nmemb - 1) * size + base; i > base; i -= size) {
		memcpy(tmp, base, size);
		memcpy(base, i, size);
		memcpy(i, tmp, size);
		heap_size--;
		HEAPIFY(base, heap_size, size, compar, base);
	}
}
